import java.util.ArrayList;
import java.util.Arrays;
import java.util.Base64;
import java.util.LinkedList;
import java.util.List;

/*
 * @lc app=leetcode.cn id=494 lang=java
 *
 * [494] 目标和
 */

// @lc code=start
class Solution {
    //回溯法
    // List<List<Integer>> res=new ArrayList<>();
    // LinkedList<Integer> path=new LinkedList<>();
    // public int findTargetSumWays(int[] nums, int target) {
    //     //原理：设正数为x,需要加负号的则为sum-x。目标值target=x-(sum-x)
    //     //则x=(sum+target)/2固定的,因此只需要满足累计和等于该值的子集和即可。
    //     if(nums.length==1){
    //         if(nums[0]==Math.abs(target)){
    //             return 1;
    //         }else{
    //             return 0;
    //         }
    //     }
    //     int sum=Arrays.stream(nums).sum();
    //     if(target>sum) return 0;
    //     if((sum+target)%2==1) return 0;
    //     int x=(sum+target)/2;
    //     Arrays.sort(nums);
    //     dfs(nums,x,0,0);
    //     return res.size();

    // }
    // private void dfs(int[] nums, int x, int startIndex,int sum) {
    //     if(sum==x){
    //         res.add(path);
    //     }
    //     if(sum>x){
    //         return;
    //     }
    //     for(int i=startIndex;i<nums.length;i++){
    //         path.add(nums[i]);
    //         sum+=nums[i];
    //         dfs(nums, x, i+1, sum);
    //         sum-=nums[i];
    //         path.removeLast();
    //     }
    // }
    //动态规划
    public int findTargetSumWays(int[] nums, int target) {
        int sum=Arrays.stream(nums).sum();
        if(Math.abs(target)>sum) return 0;//注意target为复数的情况
        int bagSize=target+sum;
        if(bagSize%2==1) return 0;
        bagSize=bagSize/2;
        int[] dp=new int[bagSize+1];
        dp[0]=1;
        for(int i=0;i<nums.length;i++){
            for(int j=bagSize;j>=nums[i];j--){
                dp[j]+=dp[j-nums[i]];//记住在求装满背包有几种方法的递推公式
            }
        }
        return dp[bagSize];
    }
}
// @lc code=end

